#pragma once

#ifndef DLL_TMAP_H
#define DLL_TMAP_H
#endif

using namespace std;


#define TMap_RED  -1
#define TMap_BLACK	1


class TNode
{
	friend TMap;
	friend TMapIterator;
	string _key;
	string _value;
	int _Color;
	TNode* _parent;
	TNode* _left;
	TNode* _right;
	void _Clear();
	TNode* _Copy(TNode*Parent);
public :
	TNode();
	TNode(int color);
	~TNode();
	TNode* After();
	TNode* Before();
	__inline const char* Value(){return _value.c_str();};
	__inline const char* Key(){return _key.c_str();};
};

static TNode* _NULL_TNODE = new TNode(TMap_BLACK);
static TNode* _NULL_TNODE_ = new TNode(TMap_BLACK);

class TMap
{
	friend TMapIterator;

	TNode* _root;
	
	void _InsertFixup (TNode*node);
	void _DeleteFixup (TNode*node,TNode*parent);
	void _RotateLeft (TNode*node);
	void _RotateRight (TNode*node);
	TNode* _Find(const char* key);
	void _Remove(TNode*node);
public :
	TMap();
	TMap* Copy();
	~TMap();
	void Clear();
	void Insert (const char* key, const char* value);
	bool IsEmpty(){return (_root==_NULL_TNODE);};
	bool Contains(const char* key);
	const char* ValueForKey(const char* key);
	bool Remove(const char* key);
	TNode* First();
	TNode* Last();
};


class TMapIterator
{
	TNode* _head;
	TNode* _tail;
public:
	TMapIterator(TMap*map);
	TNode* First(){return _head;};
	TNode* Last(){return _tail;};
	TNode* After(TNode*node);
	TNode* Before(TNode*node);
};
